package main

import (
	"fmt"
	"math"
)

/*
DAG单源最长最短距离
*/

func main() {
	n = 5
	/*
			        1
					/\
			       2  3
			      /  \/
		         4    5
	*/
	e[1] = append(e[1], edge{2, 1}, edge{3, 1})
	e[2] = append(e[2], edge{4, 1}, edge{5, 2})
	e[3] = append(e[3], edge{5, 1})

	s := 1
	dp(s)
	fmt.Println(L)
	t := 5
	if disMin[t] == inf {
		fmt.Printf("%d -> %d 没有最短路径\n", s, t)
	} else {
		fmt.Printf("%d -> %d 最短路径: %f\n", s, t, disMin[t])
	}

	if disMax[t] == -inf {
		fmt.Printf("%d -> %d 没有最长路径\n", s, t)
	} else {
		fmt.Printf("%d -> %d 最长路径: %f\n", s, t, disMax[t])
	}
}

type edge struct {
	v int
	w float64
}

const (
	maxN = 1000
)

var n, m int
var e = make([][]edge, maxN)
var in = make([]int, maxN)
var disMin = make([]float64, maxN)
var disMax = make([]float64, maxN)
var L []int

func toposort() {
	var queue []int
	for i := 1; i <= n; i++ {
		for j := 0; j < len(e[i]); j++ {
			in[e[i][j].v]++
		}
	}
	for i := 1; i <= n; i++ {
		if in[i] == 0 {
			queue = append(queue, i) //第一层 “引子”，引出后续递推遍历
		}
	}
	for len(queue) != 0 {
		u := queue[0]
		queue = queue[1:]
		L = append(L, u)
		for i := 0; i < len(e[u]); i++ {
			in[e[u][i].v]--
			if in[e[u][i].v] == 0 {
				queue = append(queue, e[u][i].v)
			}
		}
	}
	return
}

var inf = math.Inf(1)

func dp(s int) {
	toposort()

	//初始距离无穷大不可到达，如果本身就无法到达那么在遍历递推中也是无穷大结果，依然无法到达
	for i := 0; i < maxN; i++ {
		disMin[i] = inf
		disMax[i] = -inf
	}
	//自己到自己初始距离更新为0，从自己本身节点开始正确处理后续的递推数据；
	//这个初始化自己到自己的距离为0，可以称为“引子”，因为它的改变，引出所有后续数据的改变
	disMin[s] = 0
	disMax[s] = 0

	for i := 0; i < len(L); i++ {
		u := L[i]
		for j := 0; j < len(e[u]); j++ {
			disMin[e[u][j].v] = min(disMin[e[u][j].v], disMin[u]+e[u][j].w)
			disMax[e[u][j].v] = max(disMax[e[u][j].v], disMax[u]+e[u][j].w)
		}
	}
}
